Metode numerice - Aplicatii

Lucrarea 1.  Introducere. Algoritme de sortare: reordonare completa, inserare directa, algoritmul Quicksort.
Cautarea in liste ordonate.

Tema A: Algoritme de sortare

    Sortarea unui tablou de date consta in rearanjarea acestora din urma intr-o anumita ordine, crescatoare sau descrescatoare. Dintre algoritmele de sortare mai des folosite, amintim: algoritmul de reordonare completa, sortarea prin inserare directa, algoritme de tip Shell, procedura Quicksort si algoritmul Heapsort.

Tema B: Cautarea in liste ordonate

   Exista unele aplicatii care necesita parcurgerea repetata a unor liste ordonate (in cele ce urmeaza vom considera numai cazul ordonarii crescatoare), in vederea pozitionarii pe un anumit element, numit element de referinta. In functie de informatiile existente in prealabil cu privire la localizarea elementului respectiv, se disting: proceduri de localizare si proceduri de incadrare.

Reordonarea completa

    Algoritmul de reordonare completa este cel mai simplu dar, in acelasi timp, si cel mai simplist algoritm de sortare cunoscut. Ordinul de complexitate al acestui algoritm este O(n^3), unde n reprezinta dimensiunea tabloului in care se desfasoara sortarea. Principiul algoritmului de reordonare completa este descris in imaginea de mai jos.

    Se parcurg, in mod repetat urmatorii doi pasi:

  1. Se considera, pe rand, cate o pozitie de referinta in tablou i = 1,...,n-1.
  2. Pentru un index i fixat, se urmareste aducerea  in pozitia i a celui mai mic element din subsirul format de elementele x[i], x[i+1], ... , x[n]. Se compara toate elementele x[j] (j = i+1,...,n) cu elementul de referinta x[i]:

    • pentru ordonarea crescatoare : daca x[j]<x[i] se schimba intre ele elementele x[i] si x[j];

    • pentru ordonarea descrescatoare : daca x[j]>x[i] se schimba intre ele elementele x[i] si x[j].

Algoritmul de reordonare completa reprezinta in momentul de fata "preistoria" algoritmelor de sortare. El este asimilat usor, iar implementarea sa este foarte economica (sunt suficiente cateva linii de program). Din pacate, timpii de calcul indusi de complexitatea O(n^3), nu il recomanda decat pentru valori foarte mici ale dimensiunii n.

Sortarea prin inserare directa

    Algoritmul de sortare prin inserare directa realizeaza ordonarea elementelor din tablou in mai multi pasi, la fiecare pas realizandu-se inserarea unui element de referinta in pozitia corecta. Principiul acestui algoritm este urmatorul (vezi si imaginea de mai jos):

  1. Se considera, pe rand, cate un grup format din primele j elemente (j = 2,...,n). La fiecare asemenea pas, se ordoneaza crescator cele j elemente, tinand cont de faptul ca in pasii anteriori s-a asigurat ordonarea primelor j-1 elemente.
  2. Se memoreaza elementul de referinta intr-o variabila tampon Temp=x[j].
  3. Se cauta pozitia elementului de referinta Temp in interiorul subsirului ordonat x[1], x[2], ... , x[j-1] si se intercaleaza in acea pozitie. Elementul de referinta Temp se compara succesiv cu elementele care il preced, in ordinea x[j-1], x[j-2], ... , x[1] :

    • atat timp cat elementele respective au valori superioare lui Temp, acestea se deplaseaza cu un camp spre dreapta:  x[i+1] <-- x[i].
    • cand se gaseste un element x[i] < Temp, se inscrie valoarea elementului de referinta in pozitia i+1si procesul de ordonare pentru pasul j se incheie.

    Sortarea prin inserare directa economiseste un numar important de operatii de comparatie si atribuire in raport cu algoritmul de reordonare completa, avand un ordin de complexitate O(n^2). Totodata, codul sursa al unei proceduri ce implementeaza acest algoritm nu este foarte complicat. Algoritmul de sortare prin inserare directa va fi preferat algoritmului de reordonare completa, recomandandu-se pentru dimensiuni ale problemei de ordin pana la n = 20 - 30.

Algoritmul Quicksort

    Pentru valori ale dimensiunii n a sirului care se ordoneaza mai mari decat 20-30, algoritmul Quicksort este, in medie, cel mai rapid algoritm de sortare dintre cele cunoscute, avand o complexitate O(n).
    Algoritmul Quicksort originar realizeaza sortarea dupa principiul partitionarii, respectand urmatorul model (pentru ordonarea crescatoare):

  1. Din vectorul care se ordoneaza se alege un element de partitionare p, care se aduce pe prima pozitie in tablou.
  2. Se porneste cautarea simultan de  la  inceputul  si  de  la  sfarsitul  tabloului,  folosind  doi  indecsi  i = 2, 3, ...,  respectiv  j = n, n-1, ... Dupa primul indice, i, se cauta un element x[i] mai mare decat elementul de partitionare p, iar dupa indicele  j - un element x[j] mai mic decat p. Evident, elementele x[i] si x[j] ocupa pozitii incorecte in tablou si trebuie sa isi schimbe pozitiile intre ele.
  3. Procesul de cautare dupa indicii i si j continua pana cand i = j. Aceasta este pozitia corecta pe care trebuie sa o ocupe elementul de partitionare in tablou. Dupa inserarea elementului p in aceasta pozitie, toate elementele situate la stanga sa sunt mai mici decat p, in timp ce toate elementele situate la dreapta sa sunt mai mari decat p.
  4. Procesul continua prin aplicarea recurenta a aceleiasi scheme subsirurilor situate la stanga, respectiv la dreapta lui p.

    In raport cu modelul descris, schema logica din imaginea de mai jos contine urmatoarele particularitati.


         Apelul initial se va face cu Prim=1, respectiv Ultim=n (sirul complet).



Localizarea unui element in liste ordonate

    Pornind  de  la  o  lista  x[j]  (j=1, ... ,n), ale carei elemente sunt ordonate crescator sau descrescator, si o valoare xx, se cere determinarea acelui indice j* pentru care x[j*]< xx <x[j*+1].
Cea mai simpla abordare acestei probleme aplica o tehnica de tipul "injumatatirii intervalelor". Pentru cazurile in care valoarea xx iese in afara domeniului listei, se adopta urmatoarea conventie: pentru lista ordonata x[1], ... , x[n] se considera elementele fictive x[0] si x[n+1] care joaca rolul lui  "-infinit", respectiv "+infinit". O valoare a indicelui j* egala cu 0 indica situarea punctului de calcul in intervalul (-infinit, x[1]). La polul opus, daca j* = n, punctul de calcul se afla in intervalul (x[n], +infinit).
    Imaginea de mai jos ilustreaza modul de aplicare a acestei tehnici pentru cazul particular al unei liste formate din primele 256 de numere intregi pozitive.


Pornind de la intervalul global [1,256], valoarea 235 este localizata in subintervalul [232, 240] dupa cinci injumatatiri.

Incadrarea unui element in liste ordonate

    In cazul in care determinarea pozitiei elementului xx in lista x[1] ... x[n] se face in mod repetat, folosirea unei scheme de localizare de tipul celei descrise mai sus se poate dovedi neeconomica. Fiecare apel al procedurii de localizare inseamna reluarea procesului de "injumatatire" de la inceput, pentru fiecare valoare care se doreste localizata.
    In practica nu rareori se intalneste situatia in care doua valori succesive a caror pozitie in lista trebuie determinata se gasesc foarte aproape una de alta. Pentru asemenea cazuri o localizare prealabila, oricat de aproximativa ar fi ea, se poate dovedi salutara pentru identificarea mai rapida a pozitiei valorii respective in lista.
    Daca se dispune de o asemenea localizare prealabila  j*, se poate aplica o procedura de incadrare "grosiera" a valorii xx intre doua elemente din lista prin dublarea pasului, dupa care se aplica  o  procedura  de  localizare  pentru  incadrarea  stricta   a   valorii   respective. Modul de aplicare a acestei tehnici este ilustrat in imaginea de mai jos.


Daca se urmareste localizarea unei valori din vecinatatea lui 70 si se dispune de o localizare prealabila corespunzatoare valorii 7, se aplica principiul dublarii pasului (linie continua), pana la localizarea "grosiera a valorii in subintervalul [38, 70]. In continuare, se revine la modelul de injumatatire (linie intrerupta) pentru localizarea stricta.

  Aplicatii - Lista lucrarilor de laborator